// Copyright 2010, Vanya Davidenko.
// Используемая кодировка: UTF-8.

#ifndef SCRW_HTML_TEXT_EXTRACTOR_
#define SCRW_HTML_TEXT_EXTRACTOR_

#include <cstring>
#include <memory>
#include <set>
#include <map>
#include <unicode/schriter.h>
#include <unicode/uniset.h>
#include <unicode/unistr.h>
#include <unicode/utf16.h>

#include "common.h"
#include "set_recognizer.h"
#include "map_replacer.h"



namespace scrw
{

/** TODO: дополнить. Непотокобезопасный класс, выделяющий текст из html-файла.
  * Класс итерирует по code units (2 байта в UTF-16), а не кодовым точкам
  * (2 или 4 байта в UTF-16), так как разбирается только html-разметка
  * (содержимое сайта, текст, всегда просто добавляется к результату), которая
  * состоит из ASCII-символов и, следовательно, всегда представляется 2-мя
  * байтами. Это позволяет заметно ускорить процесс, так как не нужно на каждом
  * шаге проверять является ли данный unit элементом суррогата или нет.
  * При этом все значения хранятся в 32-битных переменных (UChar32), так как
  * операции сравнения получаются быстрее (на 10-15%), потому что не происходит
  * расширения типа в процессоре. */
class HtmlTextExtractor
{
 public:
    typedef ::std::map< ::std::string, icu::UnicodeString > TagReplaceMap;

    HtmlTextExtractor(const TagReplaceMap& tag_replace_map = TagReplaceMap())
        : it_(Html()),
          phtml_(NULL)
    {
        InitOmittingTagsRecognizer();
        InitEntityReplacer();
        InitTagReplacer(tag_replace_map);
    }



    HtmlTextExtractor(const HtmlTextExtractor& rhv)
        : it_(Html()),
          phtml_(NULL),
          omitting_tags_recognizer_(rhv.omitting_tags_recognizer_),
          html_entity_replacer_(rhv.html_entity_replacer_),
          tag_replacer_(rhv.tag_replacer_),
          replacements_(rhv.replacements_) {}



    icu::UnicodeString Extract(const Html& html)
    {
        PRECOND(html.isBogus() == FALSE);

        phtml_ = &html;

        // Куски текста добавляются в результат не через
        // icu::UnicodeString::opeartor+=(), а чем memcpy во внутренний буфер.
        // Это дает значительный прирост в скорости (2-3 раза).
        icu::UnicodeString result;
        UCharBuffer result_buf(result.getBuffer(html.length()), html.length());

        Slice data(phtml_, 0);  // текущий кусок данных
        Slice omitting_tag(phtml_);  // имя тега, с которого начался пропуск

        it_ = icu::StringCharacterIterator(html);

        // Если в начале идет BOM — пропускаем его.
        UChar32 c = it_.firstPostInc();
        if ( c == 0xFEFF )
        {
            c = it_.firstPostInc();
            data.Reset(it_.getIndex());
        }


        for ( UChar32 c = it_.firstPostInc() ;
              c != icu::StringCharacterIterator::DONE ;
              c = it_.nextPostInc() )
        {
            if ( c == '<' )
            {
                if ( AtTagBeginning() )
                {
                    if ( omitting_tag.empty() )
                    {
                        data.set_end(it_.getIndex() - 1);  // перед '<'
                        result_buf.Append(data);
                        const Slice tag_name = TagCycle();

                        if ( IsStartOmittingTag(tag_name) )
                            omitting_tag = tag_name;
                        else
                            result_buf.Append(TagReplacement(tag_name));

                        data.Reset(it_.getIndex());  // после тега
                    }

                    else if ( IsEndOmittingTag(omitting_tag, TagCycle()) )
                    {
                        omitting_tag.clear();
                        data.Reset(it_.getIndex());  // после тега
                    }
                }

                // Комментарии нельзя считать служебным тегом (см. ниже),
                // так как внутри них кавычки не имеют служебного назначения,
                // поэтому одиночная кавычка не является незакрытой.
                else if ( AtCommentBeginning() )
                {
                    if ( omitting_tag.empty() )
                    {
                        data.set_end(it_.getIndex() - 1);  // перед '<'
                        result_buf.Append(data);
                    }

                    CommentCycle();
                    data.Reset(it_.getIndex());  // после комментария
                }

                else if ( AtCdataBeginning() )
                {
                    if ( omitting_tag.empty() )
                    {
                        data.set_end(it_.getIndex() - 1);  // перед '<'
                        result_buf.Append(data);
                        result_buf.Append(CdataCycle());
                    }
                    else
                    {
                        CdataCycle();
                    }

                    data.Reset(it_.getIndex());  // после секции cdata
                }

                else if ( AtServiceTagBeginning() ||
                          AtXhtmlHeaderBeginning() )
                {
                    if ( omitting_tag.empty() )
                    {
                        data.set_end(it_.getIndex() - 1);  // перед '<'
                        result_buf.Append(data);
                    }

                    TagCycle();
                    data.Reset(it_.getIndex());  // после комментария
                }
            }

            else if ( c == '&' )
            {
                if ( omitting_tag.empty() )
                {
                    data.set_end(it_.getIndex() - 1);  // перед '&'
                    result_buf.Append(data);
                }

                const Slice entity = HtmlEntityCycle();
                data.Reset(it_.getIndex());  // после мнемоники

                UChar32 codepoint = -1;

                // HTML-мненоники представляются двумя формами:
                // &#UUUU;, где UUUU — кодовая точка
                // &TEXT;, где TEXT — имя мнемоники
                if ( entity.empty() )
                    continue;
                else if ( entity.data()[0] == '#' )
                    codepoint = UnicodeCodepointEntity(entity);
                else
                    codepoint = html_entity_replacer_.Replace(entity.data(),
                                                              entity.length());

                if ( codepoint != -1 )
                    result_buf.Append(codepoint);
            }
        }



        if ( omitting_tag.empty() )
        {
            data.set_end(phtml_->length());  // после всего текста
            result_buf.Append(data);
        }

        result.releaseBuffer(result_buf.length());
        return result;
    }


  private:
    HtmlTextExtractor& operator=(const HtmlTextExtractor&);

    class Slice
    {
      public:
        Slice()
            : str_(NULL),
              begin_(0),
              end_(0) {}


        Slice(const icu::UnicodeString* str,
              const int32_t begin = 0,
              const int32_t end = 0)
            : str_(str),
              begin_(begin),
              end_(end) {}


        icu::UnicodeString UnicodeString() const
        {
            return icu::UnicodeString(*str_, begin_, length());
        }

        int32_t begin() const
        {
            return begin_;
        }

        int32_t end() const
        {
            return end_;
        }

        const UChar* data() const
        {
            return str_->getBuffer() + begin_;
        }

        int32_t length() const
        {
            assert(end_ - begin_ >= 0);
            return end_ - begin_;
        }

        bool empty() const
        {
            return end_ == begin_;
        }

        void Reset(const int32_t begin)
        {
            begin_ = begin;
            end_ = str_->length();
        }

        void set_end(const int32_t end)
        {
            end_ = end;
        }

        void clear()
        {
            begin_ = 0;
            end_ = 0;
        }

      private:
        const icu::UnicodeString* str_;
        int32_t begin_;
        int32_t end_;
    };


    class UCharBuffer
    {
      public:
        UCharBuffer(UChar* buffer, const int32_t max_length)
            : buffer_(buffer),
              length_(0),
              max_length_(max_length) {}

        const UChar* buffer() const
        {
            return buffer_;
        }

        int32_t length() const
        {
            return length_;
        }

        void Append(const Slice& slice)
        {
            // memcpy не проверяет это и при записи 0 байт по адресу 0 — ошибка.
            if ( slice.empty() ) return;

            VERIFY(length_ + slice.length() <= max_length_);

            ::std::memcpy(buffer_+ length_,
                          slice.data(),
                          slice.length() * sizeof(UChar));
            length_ += slice.length();
        }

        void Append(const UChar32 c)
        {
            // Максимум 2
            VERIFY(length_ + 2 <= max_length_);
            U16_APPEND_UNSAFE(buffer_, length_, c);
        }

      private:
        UChar* buffer_;
        int32_t length_;
        int32_t max_length_;
    };


    typedef MapReplacer<UChar32> HtmlEntityReplacer;
    typedef ::std::map< ::std::string, Slice > FastTagReplaceMap;
    typedef MapReplacer<Slice> TagReplacer;



    void InitOmittingTagsRecognizer()
    {
        // Теги должны иметь обязательные закрывающие!
        // Поэтому нет тегов head и keygen, так как при отсутствии закрывающего
        // тега, пропуск текста продлится до конца страницы.
        ::std::set< ::std::string > omitting_tags;
        omitting_tags.insert("applet");
        omitting_tags.insert("audio");
        omitting_tags.insert("embed");
        omitting_tags.insert("iframe");
        omitting_tags.insert("map");
        omitting_tags.insert("meter");
        omitting_tags.insert("noembed");
        omitting_tags.insert("noframes");
        omitting_tags.insert("noscript");
        omitting_tags.insert("object");
        omitting_tags.insert("output");
        omitting_tags.insert("progress");
        omitting_tags.insert("script");
        omitting_tags.insert("source");
        omitting_tags.insert("style");
        omitting_tags.insert("video");

        omitting_tags_recognizer_ = SetRecognizer(omitting_tags, false);
    }


    void InitEntityReplacer()
    {
        // http://www.w3.org/TR/html4/sgml/entities.html
        ::std::map< ::std::string, UChar32 > entity_map;

        // Операция создания автомата очень длительная — 300 мс.
        // Для сравнения тесты с HtmlTextExtractor без entity_map
        // выполняются 3 мс, с ним — 305 мс.
        // Если такое поведение не устраивает и нужно часто создавать
        // HtmlTextExtractor, возможно, следует вынести создание entity_map.
        // из конструктора.
        entity_map["nbsp"] = 160;
        entity_map["iexcl"] = 161;
        entity_map["cent"] = 162;
        entity_map["pound"] = 163;
        entity_map["curren"] = 164;
        entity_map["yen"] = 165;
        entity_map["brvbar"] = 166;
        entity_map["sect"] = 167;
        entity_map["uml"] = 168;
        entity_map["copy"] = 169;
        entity_map["ordf"] = 170;
        entity_map["laquo"] = 171;
        entity_map["not"] = 172;
        entity_map["shy"] = 173;
        entity_map["reg"] = 174;
        entity_map["macr"] = 175;
        entity_map["deg"] = 176;
        entity_map["plusmn"] = 177;
        entity_map["sup2"] = 178;
        entity_map["sup3"] = 179;
        entity_map["acute"] = 180;
        entity_map["micro"] = 181;
        entity_map["para"] = 182;
        entity_map["middot"] = 183;
        entity_map["cedil"] = 184;
        entity_map["sup1"] = 185;
        entity_map["ordm"] = 186;
        entity_map["raquo"] = 187;
        entity_map["frac14"] = 188;
        entity_map["frac12"] = 189;
        entity_map["frac34"] = 190;
        entity_map["iquest"] = 191;
        entity_map["Agrave"] = 192;
        entity_map["Aacute"] = 193;
        entity_map["Acirc"] = 194;
        entity_map["Atilde"] = 195;
        entity_map["Auml"] = 196;
        entity_map["Aring"] = 197;
        entity_map["AElig"] = 198;
        entity_map["Ccedil"] = 199;
        entity_map["Egrave"] = 200;
        entity_map["Eacute"] = 201;
        entity_map["Ecirc"] = 202;
        entity_map["Euml"] = 203;
        entity_map["Igrave"] = 204;
        entity_map["Iacute"] = 205;
        entity_map["Icirc"] = 206;
        entity_map["Iuml"] = 207;
        entity_map["ETH"] = 208;
        entity_map["Ntilde"] = 209;
        entity_map["Ograve"] = 210;
        entity_map["Oacute"] = 211;
        entity_map["Ocirc"] = 212;
        entity_map["Otilde"] = 213;
        entity_map["Ouml"] = 214;
        entity_map["times"] = 215;
        entity_map["Oslash"] = 216;
        entity_map["Ugrave"] = 217;
        entity_map["Uacute"] = 218;
        entity_map["Ucirc"] = 219;
        entity_map["Uuml"] = 220;
        entity_map["Yacute"] = 221;
        entity_map["THORN"] = 222;
        entity_map["szlig"] = 223;
        entity_map["agrave"] = 224;
        entity_map["aacute"] = 225;
        entity_map["acirc"] = 226;
        entity_map["atilde"] = 227;
        entity_map["auml"] = 228;
        entity_map["aring"] = 229;
        entity_map["aelig"] = 230;
        entity_map["ccedil"] = 231;
        entity_map["egrave"] = 232;
        entity_map["eacute"] = 233;
        entity_map["ecirc"] = 234;
        entity_map["euml"] = 235;
        entity_map["igrave"] = 236;
        entity_map["iacute"] = 237;
        entity_map["icirc"] = 238;
        entity_map["iuml"] = 239;
        entity_map["eth"] = 240;
        entity_map["ntilde"] = 241;
        entity_map["ograve"] = 242;
        entity_map["oacute"] = 243;
        entity_map["ocirc"] = 244;
        entity_map["otilde"] = 245;
        entity_map["ouml"] = 246;
        entity_map["divide"] = 247;
        entity_map["oslash"] = 248;
        entity_map["ugrave"] = 249;
        entity_map["uacute"] = 250;
        entity_map["ucirc"] = 251;
        entity_map["uuml"] = 252;
        entity_map["yacute"] = 253;
        entity_map["thorn"] = 254;
        entity_map["yuml"] = 255;
        entity_map["fnof"] = 402;
        entity_map["Alpha"] = 913;
        entity_map["Beta"] = 914;
        entity_map["Gamma"] = 915;
        entity_map["Delta"] = 916;
        entity_map["Epsilon"] = 917;
        entity_map["Zeta"] = 918;
        entity_map["Eta"] = 919;
        entity_map["Theta"] = 920;
        entity_map["Iota"] = 921;
        entity_map["Kappa"] = 922;
        entity_map["Lambda"] = 923;
        entity_map["Mu"] = 924;
        entity_map["Nu"] = 925;
        entity_map["Xi"] = 926;
        entity_map["Omicron"] = 927;
        entity_map["Pi"] = 928;
        entity_map["Rho"] = 929;
        entity_map["Sigma"] = 931;
        entity_map["Tau"] = 932;
        entity_map["Upsilon"] = 933;
        entity_map["Phi"] = 934;
        entity_map["Chi"] = 935;
        entity_map["Psi"] = 936;
        entity_map["Omega"] = 937;
        entity_map["alpha"] = 945;
        entity_map["beta"] = 946;
        entity_map["gamma"] = 947;
        entity_map["delta"] = 948;
        entity_map["epsilon"] = 949;
        entity_map["zeta"] = 950;
        entity_map["eta"] = 951;
        entity_map["theta"] = 952;
        entity_map["iota"] = 953;
        entity_map["kappa"] = 954;
        entity_map["lambda"] = 955;
        entity_map["mu"] = 956;
        entity_map["nu"] = 957;
        entity_map["xi"] = 958;
        entity_map["omicron"] = 959;
        entity_map["pi"] = 960;
        entity_map["rho"] = 961;
        entity_map["sigmaf"] = 962;
        entity_map["sigma"] = 963;
        entity_map["tau"] = 964;
        entity_map["upsilon"] = 965;
        entity_map["phi"] = 966;
        entity_map["chi"] = 967;
        entity_map["psi"] = 968;
        entity_map["omega"] = 969;
        entity_map["thetasym"] = 977;
        entity_map["upsih"] = 978;
        entity_map["piv"] = 982;
        entity_map["bull"] = 8226;
        entity_map["hellip"] = 8230;
        entity_map["prime"] = 8242;
        entity_map["Prime"] = 8243;
        entity_map["oline"] = 8254;
        entity_map["frasl"] = 8260;
        entity_map["weierp"] = 8472;
        entity_map["image"] = 8465;
        entity_map["real"] = 8476;
        entity_map["trade"] = 8482;
        entity_map["alefsym"] = 8501;
        entity_map["larr"] = 8592;
        entity_map["uarr"] = 8593;
        entity_map["rarr"] = 8594;
        entity_map["darr"] = 8595;
        entity_map["harr"] = 8596;
        entity_map["crarr"] = 8629;
        entity_map["lArr"] = 8656;
        entity_map["uArr"] = 8657;
        entity_map["rArr"] = 8658;
        entity_map["dArr"] = 8659;
        entity_map["hArr"] = 8660;
        entity_map["forall"] = 8704;
        entity_map["part"] = 8706;
        entity_map["exist"] = 8707;
        entity_map["empty"] = 8709;
        entity_map["nabla"] = 8711;
        entity_map["isin"] = 8712;
        entity_map["notin"] = 8713;
        entity_map["ni"] = 8715;
        entity_map["prod"] = 8719;
        entity_map["sum"] = 8721;
        entity_map["minus"] = 8722;
        entity_map["lowast"] = 8727;
        entity_map["radic"] = 8730;
        entity_map["prop"] = 8733;
        entity_map["infin"] = 8734;
        entity_map["ang"] = 8736;
        entity_map["and"] = 8743;
        entity_map["or"] = 8744;
        entity_map["cap"] = 8745;
        entity_map["cup"] = 8746;
        entity_map["int"] = 8747;
        entity_map["there4"] = 8756;
        entity_map["sim"] = 8764;
        entity_map["cong"] = 8773;
        entity_map["asymp"] = 8776;
        entity_map["ne"] = 8800;
        entity_map["equiv"] = 8801;
        entity_map["le"] = 8804;
        entity_map["ge"] = 8805;
        entity_map["sub"] = 8834;
        entity_map["sup"] = 8835;
        entity_map["nsub"] = 8836;
        entity_map["sube"] = 8838;
        entity_map["supe"] = 8839;
        entity_map["oplus"] = 8853;
        entity_map["otimes"] = 8855;
        entity_map["perp"] = 8869;
        entity_map["sdot"] = 8901;
        entity_map["lceil"] = 8968;
        entity_map["rceil"] = 8969;
        entity_map["lfloor"] = 8970;
        entity_map["rfloor"] = 8971;
        entity_map["lang"] = 9001;
        entity_map["rang"] = 9002;
        entity_map["loz"] = 9674;
        entity_map["spades"] = 9824;
        entity_map["clubs"] = 9827;
        entity_map["hearts"] = 9829;
        entity_map["diams"] = 9830;
        entity_map["quot"] = 34;
        entity_map["amp"] = 38;
        entity_map["apos"] = 39;
        entity_map["lt"] = 60;
        entity_map["gt"] = 62;
        entity_map["OElig"] = 338;
        entity_map["oelig"] = 339;
        entity_map["Scaron"] = 352;
        entity_map["scaron"] = 353;
        entity_map["Yuml"] = 376;
        entity_map["circ"] = 710;
        entity_map["tilde"] = 732;
        entity_map["ensp"] = 8194;
        entity_map["emsp"] = 8195;
        entity_map["thinsp"] = 8201;
        entity_map["zwnj"] = 8204;
        entity_map["zwj"] = 8205;
        entity_map["lrm"] = 8206;
        entity_map["rlm"] = 8207;
        entity_map["ndash"] = 8211;
        entity_map["mdash"] = 8212;
        entity_map["lsquo"] = 8216;
        entity_map["rsquo"] = 8217;
        entity_map["sbquo"] = 8218;
        entity_map["ldquo"] = 8220;
        entity_map["rdquo"] = 8221;
        entity_map["bdquo"] = 8222;
        entity_map["dagger"] = 8224;
        entity_map["Dagger"] = 8225;
        entity_map["permil"] = 8240;
        entity_map["lsaquo"] = 8249;
        entity_map["rsaquo"] = 8250;
        entity_map["euro"] = 8364;

        html_entity_replacer_ = HtmlEntityReplacer(entity_map, false, -1);
    }


    void InitTagReplacer(const TagReplaceMap& tag_replace_map)
    {
        // Чтобы уменьшить число копирование объектов, храним в одной строке
        // все замены тегов и оперируем ее слайсами.

        FastTagReplaceMap fast_tag_replace_map;

        for ( TagReplaceMap::const_iterator \
              i = tag_replace_map.begin() ; i != tag_replace_map.end() ; ++i )
        {
            const int32_t begin = replacements_.length();
            replacements_.append(i->second);

            const Slice r(&replacements_, begin, begin+i->second.length());
            fast_tag_replace_map[i->first] = r;
        }

        tag_replacer_ = TagReplacer(fast_tag_replace_map, false,
                                    Slice(&replacements_, 0, 0));
    }


    // Находимся за '<'.
    bool AtTagBeginning() const
    {
        // Имена тегов состоят из латинских символов (а, значит, представляются
        // не суррогатными парами и имеют длину 1 UChar),
        // нечувствительны к регистру. Конечный тег начинается с '/'.
        // В случае выхода за границу строки charAt() возвращает 0xffff.
        const UChar32 c = phtml_->charAt(it_.getIndex());
        return ( 'a' <= c && c <= 'z' ) ||
               ( 'A' <= c && c <= 'Z' ) ||
               c == '/';  // последовательность "</" браузеры воспринимают как
                          // начало тега, в отличие от "<", которая может быть
                          // просто текстом.
    }


    // Находимся за '<'.
    // Служебными тегами в данном случае считается <!DOCTYPE>, а так же
    // внедряемые программистами в качестве условной разметки для обработки
    // через javascript (пример: на http://www.vesti.ru/doc.html?id=407164&cid=7
    // встречаются последовательности "<!? design.theme_dossier_if; ?>",
    // в которые подставляются данные через механизм регулярных выражений.
    bool AtServiceTagBeginning() const
    {
        const int32_t i = it_.getIndex();
        return phtml_->charAt(i+0) == '!';
    }


    // Находимся за '<'.
    // Текст из XHTML выделяется по тем же правилам, что и из HTML.
    // Единственное отличие — файл начинается с заголовка xml,
    // который нужно удалить.
    bool AtXhtmlHeaderBeginning() const
    {
        const int32_t i = it_.getIndex();
        return phtml_->charAt(i+0) == '?' &&
               ( phtml_->charAt(i+1) == 'x' || phtml_->charAt(i+1) == 'X' ) &&
               ( phtml_->charAt(i+2) == 'm' || phtml_->charAt(i+2) == 'M' ) &&
               ( phtml_->charAt(i+3) == 'l' || phtml_->charAt(i+3) == 'L' ) &&
               IsTagNameEnding(phtml_->charAt(i+4));
    }


    // Находимся за '<'.
    bool AtCommentBeginning() const
    {
        // Комментарий в html начинается с последовательности "<!--".
        // Данные символы не представляются суррогатными парами — длина 1 UChar.
        // В случае выхода за границу строки charAt() возвращает 0xffff.
        const int32_t i = it_.getIndex();
        return phtml_->charAt(i+0) == '!' &&
               phtml_->charAt(i+1) == '-' &&
               phtml_->charAt(i+2) == '-';
    }


    // Находимся за '<'.
    bool AtCdataBeginning()
    {
        // Секция CDATA начинается с последовательности символов "<![CDATA[".
        // Регистр не учитывается. Все символы принадлежат ASCII,
        // а, значит, не представляются суррогатными парами и имеют длину
        // 1 UChar. В случае выхода за границу строки charAt возвращает 0xffff.
        const int32_t i = it_.getIndex();
        return   phtml_->charAt(i+0) == '!' &&
                 phtml_->charAt(i+1) == '[' &&
               ( phtml_->charAt(i+2) == 'C' || phtml_->charAt(i+2) == 'c' ) &&
               ( phtml_->charAt(i+3) == 'D' || phtml_->charAt(i+3) == 'd' ) &&
               ( phtml_->charAt(i+4) == 'A' || phtml_->charAt(i+4) == 'a' ) &&
               ( phtml_->charAt(i+5) == 'T' || phtml_->charAt(i+5) == 't' ) &&
               ( phtml_->charAt(i+6) == 'A' || phtml_->charAt(i+6) == 'a' ) &&
                 phtml_->charAt(i+7) == '[';
    }


    bool IsStartOmittingTag(const Slice& tag) const
    {
        return omitting_tags_recognizer_.Check(tag.data(), tag.length());
    }


    bool IsEndOmittingTag(const Slice& omitting_tag,
                          const Slice& found_tag) const
    {
        return found_tag.data()[0] == '/' &&
               phtml_->caseCompareBetween(
                   omitting_tag.begin(),
                   omitting_tag.begin() + omitting_tag.length(),
                   *phtml_, found_tag.begin() + 1,
                   found_tag.begin() + found_tag.length(),
                   0) == 0;
    }


    Slice TagReplacement(const Slice& tag_name) const
    {
        const UChar* begin = tag_name.data();
        int32_t length = tag_name.length();
        if ( tag_name.data()[0] == '/' )
        {
            begin++;
            length--;
        }

        const Slice result = tag_replacer_.Replace(begin, length);

        if ( result.empty() )
            return result;

        // На всякий случай создаем новый Slice, так как возможно было
        // копирование HtmlTextExtractor и указатель на replacements_ изменился.
        // Возможным решением было бы хранение replacements_ в куче, но тогда
        // пришлось бы использовать счетчик ссылок, что усложнило бы код.
        // Таким образом, данное решение, не идеальное, но быстрое и работающее.
        return Slice(&replacements_, result.begin(), result.end());
    }


    // Вход: за '<'.
    // Выход: за '>' или EOF.
    // Возвращаемое значение: имя тега.
    Slice TagCycle()
    {
        bool between_single_quotes = false;
        bool between_double_quotes = false;

        const Slice tag_name = TagNameCycle();

        // Находимся в разделителе (пробел после имени тега или '>').
        // В случае, если тег имеет вид <tag_name> — выходим в первом break.
        for ( UChar32 c = it_.nextPostInc() ;
              c != icu::StringCharacterIterator::DONE ;
              c = it_.nextPostInc() )
        {
            if ( c == '>' && !between_single_quotes && !between_double_quotes )
                break;

            else if ( c == '\'' && !between_double_quotes )
                between_single_quotes = !between_single_quotes;

            else if ( c == '\"' && !between_single_quotes )
                between_double_quotes = !between_double_quotes;
        }

        return tag_name;
    }


    // Вход: за '<'.
    // Выход: в пробельном символе после имени тега или '>', или EOF.
    // Возвращаемое значение: имя тега.
    Slice TagNameCycle()
    {
        UChar32 c = it_.nextPostInc();

        // В случае, если это был тег вида с юникодными именем, записываемым
        // суррогатными парами, возврат на -1 будет некорректным, но ничего
        // страшного не произойдет (данная последовательность не будет найдена
        // в tag_replacements_ и omitting_tags_ и отброшена).
        Slice tag_name(phtml_, it_.getIndex() - 1);

        // hasNext() медленнее, чем проверка кода возврата nextPostInc().
        for ( ; !IsTagNameEnding(c) && c != icu::StringCharacterIterator::DONE ;
              c = it_.nextPostInc() )
            continue;
        it_.move(-1, icu::StringCharacterIterator::kCurrent);

        tag_name.set_end(it_.getIndex());
        return tag_name;
    }


    bool IsTagNameEnding(const UChar32 c) const
    {
        // Имя тега заканчивается разделителем — пробельным символом или '>'.
        // В случае выхода за границу строки charAt() возвращает 0xffff.
        return c == ' ' || c == '\t' || c == '>';
    }


    // Вход: за '<'.
    // Выход: за закрывающей последовательностью символов или EOF.
    // Возвращаемое значение: содержимое CDATA.
    Slice CdataCycle()
    {
        // Перепрыгиваем "![CDATA[" — 8 позиций без суррогатных пар.
        it_.move(8, icu::StringCharacterIterator::kCurrent);

        Slice cdata(phtml_, it_.getIndex());

        // В случае пустой секции CDATA находимся в первой ']' и сразу выходим.
        for ( ; !AtCdataEnding() && it_.hasNext() ; it_.nextPostInc() )
            continue;

        cdata.set_end(it_.getIndex());

        // Перепрыгиваем "]]>" — 3 позиции без суррогатных пар.
        // В случае EOF ничего не произойдет.
        it_.move(3, icu::StringCharacterIterator::kCurrent);
        return cdata;
    }


    // Возможно, находимся в первой ']'.
    bool AtCdataEnding() const
    {
        // Секция CDATA заканчивается последовательностью символов "]]>".
        // Все символы принадлежат ASCII, а, значит, не представляются
        // суррогатными парами и имеют длину 1 UChar.
        // В случае выхода за границу строки charAt возвращает 0xffff.
        const int32_t i = it_.getIndex();
        return phtml_->charAt(i+0) == ']' &&
               phtml_->charAt(i+1) == ']' &&
               phtml_->charAt(i+2) == '>';
    }


    // Вход: за '<'.
    // Выход: за закрывающей последовательностью символов или EOF.
    void CommentCycle()
    {
        // Комментарий должен начинаться с "<!--", но может завершаться как
        // "--      >".

        // Перепрыгиваем "!--" — 3 позиции без суррогатных пар.
        it_.move(3, icu::StringCharacterIterator::kCurrent);

        // В случае пустого комментария находимся в первом '-' и сразу выходим.
        for ( ; !AtCommentEnding() && it_.hasNext() ; it_.nextPostInc() )
            continue;

        for (  UChar32 c = it_.nextPostInc() ;
               c != '>' && it_.hasNext() ;
               c = it_.nextPostInc() )
            continue;
    }



    // Возможно, находимся в первом '-'.
    bool AtCommentEnding() const
    {
        // Содержимое комментария в html заканчиваются последовательностью "--".
        // Комментарий, как элемент разметки заканчивается '>'.
        // Между этими двумя последовательности могут находиться пробельные
        // символы.
        // Данные последовательности не представляются суррогатными
        // парами — длина 1 UChar. В случае выхода за границу строки charAt()
        // возвращает 0xffff.
        const int32_t i = it_.getIndex();
        return phtml_->charAt(i+0) == '-' &&
               phtml_->charAt(i+1) == '-';
    }


    // Вход: за '<'.
    // Выход: в пробельном символе после ';' или EOF.
    // Возвращаемое значение: последовательность символов между '&' и ';'.
    Slice HtmlEntityCycle()
    {
        UChar32 c = it_.nextPostInc();

        Slice html_entity(phtml_, it_.getIndex() - 1);

        // hasNext() медленнее, чем проверка кода возврата nextPostInc().
        for ( ; !AtEntityEnding(c) && c != icu::StringCharacterIterator::DONE ;
              c = it_.nextPostInc() )
            continue;

        html_entity.set_end(it_.getIndex() - 1);

        // Мнемоника должна завершаться ';', но если данного символа нет
        // браузеры обычно идут до разделителя. Повторяем это поведение,
        // что бы не искать отсутствующий ';' до конца файла.
        if ( c != icu::StringCharacterIterator::DONE && c != ';' )
            it_.previous();

        return html_entity;
    }


    bool AtEntityEnding(const UChar32 c) const
    {
        // Мнемоника должна завершаться ';',
        // но здесь повторяется поведение браузеров.
        return c == ';' ||
              ( ! ( ( 'a' <= c && c <= 'z' ) ||
                    ( 'A' <= c && c <= 'Z' ) ||
                    ( '0' <= c && c <= '9' ) ||
                    c == '#' ) );
    }


    UChar32 UnicodeCodepointEntity(const Slice& entity) const
    {
        int base = 10;
        int32_t begin_pos = 1;
        if ( entity.data()[1] == 'x' )
        {
            base = 16;
            begin_pos = 2;
        }

        if ( begin_pos == entity.length() )
            return -1;

        UChar32 codepoint = 0;
        for ( int32_t i = begin_pos ; i != entity.length() ; ++i )
        {
            const UChar32 c = entity.data()[i];
            int value = 0;

            if ( base == 10 )
            {
                if ( !IsDecChar(c) )
                    return -1;
                value = DecValue(c);
            }
            else
            {
                assert(base == 16);
                if ( !IsHexChar(c) )
                    return -1;
                value = HexValue(c);
            }

            codepoint = base * codepoint + value;

            if ( codepoint > 0x10FFFF )
                return -1;
        }

        return codepoint;
    }


    bool IsDecChar(const UChar32 c) const
    {
        return '0' <= c && c <= '9';
    }

    int DecValue(const UChar32 c) const
    {
        return c - '0';
    }


    bool IsHexChar(const UChar32 c) const
    {
        return IsDecChar(c) ||
                ( 'a' <= c && c <= 'f' ) ||
                ( 'A' <= c && c <= 'F' );
    }

    int HexValue(const UChar32 c) const
    {
        if ( IsDecChar(c) )
            return DecValue(c);

        if ( 'a' <= c && c <= 'f' )
            return c - 'a' + 10;

        if ( 'A' <= c && c <= 'F' )
            return c - 'A' + 10;

        assert(0);
        return -1;
    }


    icu::StringCharacterIterator it_;
    const Html* phtml_;

    SetRecognizer omitting_tags_recognizer_;
    HtmlEntityReplacer html_entity_replacer_;
    TagReplacer tag_replacer_;
    icu::UnicodeString replacements_;
};

}

#endif  // SCRW_HTML_TEXT_EXTRACTOR_
